排序算法对比

冒泡排序

思路：比较相邻项，如果第一个比第二个大，则交换他们，元素向上移动，好像气泡升至表面
时间复杂度：O(n^2)

const arr = [5, 1, 0, 2, 8, 9];
function bubbleSort (arr) {
    let len = arr.length;
    let temp, flag = false;
    for (let i = 0; i < len; i++) {
        for(let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = true;
            }
        }
        if(!flag) break;
    }
    return arr;
}
console.log(bubbleSort(arr));

选择排序

思路：找到最小值的index与第一位交换，接着第二小的放第二位
时间复杂度：O(n^2)

const arr = [5, 1, 0, 2, 8, 9];
function selectionSort (arr) {
    const len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len; i++) {
        minIndex = i;
        for (j = i; j < len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

console.log(selectionSort(arr));

插入排序

思路：假定第一位已经排好序了，接着和第二项进行比较，确定第二项插入位置，这样前两项排好序了，第三项分别和第二项、第一项比较，以此类推
复杂度：排序小型数组优于选择和冒泡

const arr = [5, 1, 0, 2, 8, 9];

function insertSort (arr) {
    const len = arr.length;
    let j, temp;
    for (let i = 1; i < len; i++) {
        j = i;
        temp = arr[i];
        while (j > 0 && arr[j-1] > temp) {
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            j--;
        }
    }
    return arr;
}

console.log(insertSort(arr));

归并排序

思路：将原始数组分割直至只有一个元素的子数组，然后开始归并。归并过程也会完成排序，直至原始数组完全合并并完成排序。
复杂度：O(nlogn)

const arr = [5, 1, 0, 2, 8, 9];

function mergeSort (arr) {
    return mergeSortRec(arr);
}

function mergeSortRec (arr) {
    const len = arr.length;
    if (len === 1) {
        return arr;
    }
    const mid = Math.floor(len / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid, len);
    return merge(mergeSortRec(left), mergeSortRec(right));
}

function merge(left, right) {
    let result = [];
    let il = 0, ir = 0;
    while(il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il]);
            il++;
        } else {
            result.push(right[ir]);
            ir++;
        }
    }

    while (il < left.length){
        result.push(left[il++]);
    }

    while (ir < right.length){
        result.push(right[ir++]);
    }
    return result;
}

console.log(mergeSort(arr));

快速排序

思路：选定数组中间值，拆分左右数组，左右指针向中间移动最终使数组左边均小于中间值，右边均大于中间值，得到左右两个数组继续
时间复杂度：O(nlogn)

const arr = [14, 3, 15, 7, 2, 76, 11];
function quickSort(arr) {
    quick(arr, 0, arr.length - 1);
    return arr;
}

function quick(arr, li, ri) {
    let index;
    if (arr.length > 1) {
        index = partition(arr, li, ri);
        if (li < index - 1) {
            quick (arr, li, index - 1);
        }

        if (ri > index) {
            quick (arr, index, ri);
        }
    }
}

function partition(arr, li, ri) {
    const pivot = arr[Math.floor((li + ri) / 2)];
    let i = li, j = ri, temp;
    while(i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            // 交换arr[i]和arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--
        }
    }
    return i;
}
console.log(quickSort(arr));